package cn.suchan.jianzhi.q26_convert;

import java.util.ArrayList;
import java.util.Collections;

/**
 * 知识点：二叉搜索树与双向链表
 * 题目描述
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
 * 要求不能创建任何新的结点，只能调整树中结点指针的指向。
 *
 * @author suchan
 * @date 2019/05/29
 */
public class Solution {

    /**
     * 这种写法是理解错题意了，一开始的理解是把二叉搜索树变成排序之后的一个链表形式。
     * 这里就是将根节点变成左节点的右节点、右节点的左节点，即：
     * #           10
     * #         /    \
     * #       4       12
     * #      /  \    /   \
     * #     2   8   11   13
     * 变成：
     * #     2   8   11   13
     * #      \ /     \   /
     * #       4       12
     * #       \      /
     * #         10
     *
     * @param pRootOfTree
     * @return
     */
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null
                || (pRootOfTree.left == null && pRootOfTree.right == null)) {
            return pRootOfTree;
        }

        // 获取所有子树
        ArrayList<TreeNode> nodeList = new ArrayList();
        nodeList.add(pRootOfTree);
        for (int i = 0; i < nodeList.size(); i++) {
            if (nodeList.get(i).left != null) {
                nodeList.add(nodeList.get(i).left);
            }
            if (nodeList.get(i).right != null) {
                nodeList.add(nodeList.get(i).right);
            }
        }

        // 把每个节点变成其左节点的右节点，其右节点的左节点
        TreeNode min = pRootOfTree;
        for (int i = nodeList.size() - 1; i >= 0; i--) {
            TreeNode node = nodeList.get(i);
            if (node.left != null) {
                node.left.right = node;
                node.left = null;
            }
            if (node.right != null) {
                node.right.left = node;
                node.right = null;
            }
            if (node.val < min.val) {
                min = node;
            }
        }
        return min;
    }

    /**
     * 题目的意思应该是这种写法，即将一个二叉搜索树的所有节点进行排序，然后在一次进行连接。
     * 如：
     * #                       10
     * #                    /     \
     * #                  4       12
     * #                /   \    /   \
     * #               2    8   11   13
     * #             /  \  / \
     * #            1   3 6  9
     * #                /  \
     * #               7   8
     * 变成排好序的双向链表：
     * #  ->    ->    ->    ->    ->    ->    ->    ->    ->     ->     ->     ->
     * 1     2     3     4     5     6     7     8     9     10     11     12     13
     * # <-    <-    <-    <-    <-    <-    <-    <-    <-     <-      <-     <-
     * (或者这样表示：1↔2↔3↔4↔5↔6↔7↔8↔9↔10↔11↔12↔13)
     * 也就是从左开始读的顺序是：
     * 1->2->3->4->5->6->7->8->9->10->11->12->13
     * 从右开始读的顺序是：
     * 13->12->11->10->9->8->7->6->5->4->3->2->1
     *
     * @param pRootOfTree
     * @return
     */
    public TreeNode Convert1(TreeNode pRootOfTree) {
        if (pRootOfTree == null
                || (pRootOfTree.left == null && pRootOfTree.right == null)) {
            return pRootOfTree;
        }

        // 获取所有子树
        ArrayList<TreeNode> nodeList = new ArrayList();
        nodeList.add(pRootOfTree);
        for (int i = 0; i < nodeList.size(); i++) {
            if (nodeList.get(i).left != null) {
                nodeList.add(nodeList.get(i).left);
            }
            if (nodeList.get(i).right != null) {
                nodeList.add(nodeList.get(i).right);
            }
        }

        // 把所有节点的左右节点清空
        for (int i = 0; i < nodeList.size(); i++) {
            nodeList.get(i).left = null;
            nodeList.get(i).right = null;
        }

        // 对所有节点进行排序
        for (int i = 0; i < nodeList.size() - 1; i++) {
            for (int j = i + 1; j < nodeList.size(); j++) {
                if (nodeList.get(j).val < nodeList.get(i).val) {
                    Collections.swap(nodeList, i, j);
                    /*TreeNode temp = nodeList.get(i);
                    nodeList.set(i, nodeList.get(j));
                    nodeList.set(j, temp);*/
                }
            }
        }

        // 对每个节点进行双向连接
        for (int i = 0; i < nodeList.size() - 1; i++) {
            nodeList.get(i).right = nodeList.get(i + 1);
            nodeList.get(i + 1).left = nodeList.get(i);
        }
        return nodeList.get(0);
    }

    public static void main(String[] args) {

        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);
        TreeNode node9 = new TreeNode(9);
        TreeNode node10 = new TreeNode(10);
        TreeNode node11 = new TreeNode(11);
        TreeNode node12 = new TreeNode(12);
        TreeNode node13 = new TreeNode(13);

        node10.left = node4;
        node10.right = node12;
        node4.left = node2;
        node4.right = node8;
        node12.left = node11;
        node12.right = node13;
        node2.left = node1;
        node2.right = node3;
        node8.left = node6;
        node8.right = node9;
        node6.left = node5;
        node6.right = node7;

        Solution solution = new Solution();
        //TreeNode convert = solution.Convert(node10);
        solution.Convert1(node10);
    }
}
